← All Articles

[SW Expert Academy] 5656. 벽돌 깨기

Posted on

문제 :

구술을 쏘아 벽돌을 깨트리는 게임을 하려고 한다.

구슬은 N번만 쏠 수 있고, 벽돌들의 정보는 아래와 같이 W x H 배열로 주어진다.

( 0 은 빈 공간을 의미하며, 그 외의 숫자는 벽돌을 의미한다. )

image

게임의 규칙은 다음과 같다.

① 구슬은 좌, 우로만 움직일 수 있어서 항상 맨 위에 있는 벽돌만 깨트릴 수 있다.

② 벽돌은 숫자 1 ~ 9 로 표현되며,

구술이 명중한 벽돌은 상하좌우로 ( 벽돌에 적힌 숫자 - 1 ) 칸 만큼 같이 제거된다.


아래는 벽돌에 적힌 숫자와, 구술이 명중했을 시 제거되는 범위의 예이다.

image

③ 제거되는 범위 내에 있는 벽돌은 동시에 제거된다.


예를 들어 아래와 같이 4 번 벽돌에 구술이 명중할 경우,

image

9번 벽돌은 4 번 벽돌에 반응하여, 동시에 제거된다.

image

④ 빈 공간이 있을 경우 벽돌은 밑으로 떨어지게 된다.

N 개의 벽돌을 떨어트려 최대한 많은 벽돌을 제거하려고 한다.

N, W, H, 그리고 벽돌들의 정보가 주어질 때,

▶ 남은 벽돌의 개수를 구하라!


[ 제약 사항 ]

  1. 1 ≤ N ≤ 4
  2. 2 ≤ W ≤ 12
  3. 2 ≤ H ≤ 15

입력 :

가장 첫 줄에는 총 테스트 케이스의 개수 T 가 주어지고,

그 다음 줄부터 T 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 N, W, H 가 순서대로 공백을 사이에 두고 주어지고,

다음 H 줄에 걸쳐 벽돌들의 정보가 1 줄에 W 개씩 주어진다.


출력 :

출력은 #t 를 찍고 한 칸 띄운 다음 정답을 출력한다.

(t 는 테스트 케이스의 번호를 의미하며 1 부터 시작한다)



풀이 :

구슬이 벽돌을 깼을 때 연쇄적으로 깨지고 다시 벽돌이 중력에 따라 아래로 떨어지는 것을 구현하는 것이 조금은 까다로울 수 있지만,

그 과정을 제외하면 구슬을 던지는 횟수가 4회인 점에다가 map의 크기가 최대 15*12 배열인 점에 따라 완전 탐색으로 답을 도출 할 수 있다.


[ 세부 구현 사항 ]

  1. 완전 탐색으로 각 구슬이 모든 column 위치에서 4회 반복 했을 때 가장 적게 남는 구슬 갯수를 도출한다. 그를 위해서 현재 벽돌들의 위치를 나타내는 map 배열은 매개변수로 받아 관리해야 한다. => map 배열의 경우 재귀 함수별로 다른 벽돌 상태를 가지기 때문
  2. 매개변수로 받은 map 배열은 본래의 벽돌 위치를 저장하고 있기 때문에 수정이 일어나선 안된다. 대신에 tempmap이라는 이차원 배열을 만들어 map의 정보를 저장한 후 현재에서 구슬을 던졌을 때 벽돌의 상태를 저장시켜주어야 한다. => 벽돌 상태는 매번 업데이트 되고 초기화 되어서 사용되어야 한다. 이 점 또한 구현해주어야 함.
  3. 구슬을 쳐서 벽돌이 연쇄적으로 깨지는 과정은 queue를 사용하여 구현했다. 구슬이 벽돌을 칠 경우 네 방향으로 연쇄적으로 부서지는 벽돌을 탐색하며 0일 경우 계속 진행, 1일 경우 0으로 변환, 1 이상일 경우에는 큐에 저장하여 큐가 빌 때까지 연쇄 탐색을 진행한다.
  4. 벽돌이 아래로 떨어져서 저장되는 과정은 다음 재귀 함수로 진행되었을 경우에 tempmap이 map 정보를 저장할 때 구현된다. map의 각 column 가장 아래행부터 탐색하여 tempmap 컬럼에 저장하는 방식을 사용한다.


코드 :

코드 보기/접기 
#include <iostream>
#include <utility>
#include <queue>

#define pii pair<int, int>

using namespace std;
int n, width, height, minans;
int di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};

int min(int a, int b) {
    if (a >= b) return b;
    return a;
}

void recursiveProcess(int order, int map[][12]) {
    if (order >= n) {
        int cnt = 0;
        for (int i = 0; i < height; i++)
            for (int j = 0; j < width; j++)
                if (map[i][j]) cnt++;

        minans = min(minans, cnt);
        return;
    }

    queue<pii > q;
    for (int col = 0; col < width; col++) {
        int tempmap[15][12]{0};

        for (int j = 0; j < width; j++) {
            int idx = height - 1;
            for (int i = height - 1; i >= 0; i--)
                if (map[i][j]) tempmap[idx--][j] = map[i][j];
        }

        int curx = 0, cury = col;
        while (curx < height) {
            if (tempmap[curx][cury]) {
                q.push(pii(curx, cury));
                break;
            }
            curx++;
        }

        while (!q.empty()) {
            int cmpx = q.front().first, cmpy = q.front().second, cmplen = tempmap[cmpx][cmpy] - 1;
            tempmap[cmpx][cmpy] = 0;
            q.pop();

            for (int k = 0; k < 4; k++) {
                for (int t = 1; t <= cmplen; t++) {
                    int tempx = cmpx + di[k] * t, tempy = cmpy + dj[k] * t;
                    if (tempx < 0 || tempx >= height || tempy < 0 || tempy >= width) continue;
                    if (!tempmap[tempx][tempy]) continue;
                    else if (tempmap[tempx][tempy] == 1) tempmap[tempx][tempy] = 0;
                    else q.push(pii(tempx, tempy));
                }
            }
        }

        recursiveProcess(order + 1, tempmap);
    }
}

void testCase() {
    cin >> n >> width >> height;
    minans = 10000;

    int map[15][12];

    for (int i = 0; i < height; i++)
        for (int j = 0; j < width; j++)
            cin >> map[i][j];

    recursiveProcess(0, map);
}

int main(int argc, char **argv) {
    int test_case;
    int T;

    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        testCase();
        cout << '#' << test_case << ' ' << minans << '\n';
    }
    return 0;
}


AlgorithmalgorithmSW ExpertC++